The Jump Logic
Imagine merging $\text{Left}: [2, 4, 6]$ and $\text{Right}: [1, 3, 5]$.
- We pick $1$ (from Right). It is smaller than $2$ (from Left).
- Because $\text{Left}$ is sorted, if $1 < 2$, then $1 < 4$ and $1 < 6$ too!
- The number $1$ has "jumped over" **all remaining items** in the Left list.
-
The Formula:
When picking from $\text{right}$, the number of inversions found is $\text{len}(\text{left}) - i$ (where $i$ is the current index).
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
# Return TWO values: list, count
left, left_inv = ____
right, right_inv = ____
merged = []
i = 0; j = 0
# Accumulate previous counts
current_inversions = 0 + left_inv + right_inv
while i < len(left) and j < len(right):
if ____:
merged.append(left[i])
i += 1
else:
# right[j] is smaller (Inversion!)
merged.append(right[j])
j += 1
# MAGIC LINE: How many did we jump?
current_inversions += ____
merged.extend(left[i:])
merged.extend(right[j:])
return merged, current_inversions
Copied!